package com.cty._03_SolutionSeekingMindset._32_02_PrintTreeInLines;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @Auther: cty
 * @Date: 2020/7/11 15:23
 * @Description: 面试题32（二）：分行从上到下打印二叉树
 * 题目：从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。
 * @version: 1.0
 */
public class PrintTreeInLines {

    /**
     * 队列实现
     * @param treeRoot
     */
    public static void printTree(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return;

        Queue<BinaryTreeNode> queue = new ArrayDeque<>();
        queue.add(treeRoot);
        int currentLineNodeNum = 1;
        int nextLineNodeNum = 0;

        while(!queue.isEmpty()){
            while(currentLineNodeNum-- > 0){
                BinaryTreeNode temp = queue.remove();
                System.out.print(temp.value + " ");

                if(temp.leftChild != null){
                    queue.add(temp.leftChild);
                    nextLineNodeNum++;
                }
                if(temp.rightChild != null){
                    queue.add(temp.rightChild);
                    nextLineNodeNum++;
                }
            }  // end while

            System.out.println();

            currentLineNodeNum = nextLineNodeNum;
            nextLineNodeNum = 0;
        }  // end while queue isEmpty
    }  // end printTree()

}  // end class

class BinaryTreeNode{
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}

    public BinaryTreeNode(int value){this.value = value;}
}  // end BinaryTreeNode
